/*
leetcode 219. 存在重复元素 II
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，
满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false


提示：

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5
*/

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) {

    unordered_map<int, int> numIndexMap; // 哈希表存储数字及其下标

    for (int i = 0; i < nums.size(); i++) {
        
        // 检查当前数字是否在哈希表中，如果不等式为 true，则表示 nums[i] 已经在哈希表中，可能是重复元素
        //numIndexMap.find(nums[i])：表示查找哈希表 numIndexMap 中是否包含键值为 nums[i] 的元素。
            //如果找到该元素，返回该元素的迭代器。
            //如果找不到该元素，返回哈希表的 end() 迭代器。
        if (numIndexMap.find(nums[i]) != numIndexMap.end()) {
            
            // 判断下标差值是否小于等于 k，numIndexMap[nums[i]]是键对应的值，即上次该数字在数组中的下标
            if (i - numIndexMap[nums[i]] <= k) {
                return true;
            }
        }
        
        // 更新当前数字的最新下标
        numIndexMap[nums[i]] = i;
    }
    return false; // 遍历完仍未找到符合条件的元素
}

int main() {
    vector<int> nums = {1, 2, 3, 1};
    int k = 3;
    cout << (containsNearbyDuplicate(nums, k) ? "true" : "false") << endl;

    nums = {1, 0, 1, 1};
    k = 1;
    cout << (containsNearbyDuplicate(nums, k) ? "true" : "false") << endl;

    nums = {1, 2, 3, 1, 2, 3};
    k = 2;
    cout << (containsNearbyDuplicate(nums, k) ? "true" : "false") << endl;

    return 0;
}
/*
假设输入为：
nums = [1, 2, 3, 1]，k = 3

初始化
定义一个哈希表 numIndexMap，存储数组中每个元素的最近一次出现位置。

遍历数组，从第一个元素开始处理。

第 1 步：元素 1（索引 0）
当前元素：nums[0] = 1
哈希表：numIndexMap = {}（空）
1 不在哈希表中，将其加入哈希表：numIndexMap = {1: 0}

第 2 步：元素 2（索引 1）
当前元素：nums[1] = 2
哈希表：numIndexMap = {1: 0}
2 不在哈希表中，将其加入哈希表：numIndexMap = {1: 0, 2: 1}

第 3 步：元素 3（索引 2）
当前元素：nums[2] = 3
哈希表：numIndexMap = {1: 0, 2: 1}
3 不在哈希表中，将其加入哈希表：numIndexMap = {1: 0, 2: 1, 3: 2}

第 4 步：元素 1（索引 3）
当前元素：nums[3] = 1
哈希表：numIndexMap = {1: 0, 2: 1, 3: 2}
1 已经在哈希表中，上次出现的索引为 numIndexMap[1] = 0。
检查索引差：3 - 0 = 3，满足条件 ≤k。
返回 true。

输出
由于在第 4 步找到了满足条件的元素对，算法返回 true。


*/
